1. Field of the Invention
The present invention relates to a calculating apparatus for performing calculations in such a manner that two integers are multiplied and its result is divided by another integer to obtain the residue, that is integers A, B and N are subjected to a modular multiplication A.multidot.B mod N. More particularly, the present invention relates to a calculating apparatus for performing a modular multiplication of large digit integers suitable for use in a cryptographic scheme such as an RSA cryptosystem.
Also the present invention relates to a communication method which uses the aforesaid calculating apparatus for executing encryption of the contents transmitted and decryption of the cryptogram received and which is used in various communication services such as the home banking, farm banking, electronic mail and the electronic post services in a computer network.
2. Description of the Related Art
Recently, a cryptographic scheme for protecting the content of data has become important with a remarkable advance in an information communication system which uses a computer network. In particular, a high speed cryptographic scheme has become necessary with the tendency of increasing the speed in the network and enlarging its capacity.
Hitherto, it has been known that the encryption methods are classified into a public-key cryptosystem and a common-key cryptosystem. Among others, the public-key criptosystem has been attracting attention because of its advantages that the administration of its key can easily be performed and the digital signature can be performed as compared with the common-key cryptosystem.
An RSA cryptography is a typical cryptograph of the public-key cryptosystem and is considered to be the most advantageous public-key cryptograph.
The RSA cryptography is calculated by a modular exponentiation: C=M.sup.e mod N (where C, M, N and e are integers). The modular exponentiation can be performed by repeating modular multiplications: D=A.multidot.B mod N (where A, B and D are integers). However, since N and e must be 512 bits or more to secure the safety against unlawful cryptanalysis in the RSA cryptography, a problem of an excessively large computational complexity arises.
Hitherto, the types of the modular multiplication circuit for large digit integers that perform a calculation of R=A.multidot.B mod N by using integers A, B and N are basically classified into two methods. One of them is performed by dividing the modular multiplication into a multiplication: C=A.multidot.B and a residue calculation: D=C mod N. Another method is performed by, n times, subjecting a.sub.n-i (i=1, . . . , n) divided by A for each bit to a partial product and residue calculations in each of which R=2.multidot.R+a.sub.n-i .multidot.B mod N (i=1 . . . N) is performed.
The former method exhibits advantages in that the structure can be relatively simplified and the control can be easily performed because of its structure usually having a multiplying circuit and a residue calculation circuit formed into a pipeline. However, there arises a problem in that a desired apparatus cannot be realized with a small circuit because the aforesaid method must have a memory for temporarily storing multiplication result C and a multiplying circuit and a residue calculation circuit must be separated.
On the other hand, the latter method exhibits an advantage in that the size of the circuit can be considerably reduced because its process comprises the steps of the partial product calculation and the residue calculation of the result of the partial product calculation. However, problems arise in that a delay time generated due to the carry involved in the partial product and residue calculations cannot be eliminated, the size of the carrying bit register cannot be reduced, and a discrimination whether or not R&gt;N must be made for a residue calculation with modulo N.
Another problem takes place in that the processing speed will be decreased due because it is necessary to provide clocks or more in each multiplication steps because the multiplication is usually performed by adding B to 2.multidot.R in only a case where a.sub.n-i =1.
In a case where the aforesaid problems are desired to be overcome by providing a large-digit multiplier and a divisor which must be used in a case where an assumption is made that the division a.sub.n-i of A is plural bits, there arises another problem in that there is no ROM and a cell-library with which the aforementioned large-digit multiplier and the divisor can be realized. If the large-digit multiplier and the divisor are designed, a problem arises in that the desired circuit is too complex in its structure in a case where the structure of the circuit for a small-digit multiplier and that of the divisor are simply expanded.
As described above, the conventional method suffers from a variety of problems, so that an efficient modular multiplication circuit has not been realized as yet.